import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

public class DAY0423 {
    
      public class ListNode {
          int val;
          ListNode next;

          ListNode(int x) {
              val = x;
              next = null;
          }
      }
    //剑指 Offer 52. 两个链表的第一个公共节点
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> nums = new HashSet<ListNode>();
        ListNode temp = headA;
        while (temp != null){
            nums.add(temp);
            temp = temp.next;
        }

         temp = headB;
        while (temp != null){
            if(nums.contains(temp)){
                return temp;
            }
            temp = temp.next;
        }
        return null;
    }

    //剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
    public int[] exchange(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        int left = 0, right = n - 1;
        for (int num : nums) {
            if (num % 2 == 1) {
                res[left++] = num;
            } else {
                res[right--] = num;
            }
        }
        return res;
    }

    //剑指 Offer 57. 和为s的两个数字
    public int[] twoSum(int[] nums, int target) {
          int i = 0;
          int j = nums.length - 1;
        while (i < j){
            int s = nums[i] + nums[j];
            if(s > target){
                j = j-1;
            } else if (s < target) {
                i = i+1;
            }else{
                return new int[]{nums[i] , nums[j]};
            }
        }
        return new int[0];
    }
}
